1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include<bits/stdc++.h>
using namespace std;
typedef long long s64;
const int ONE = 1000005;
const int MOD = 1e9;
const int INF = 2147483640;
int get()
{
int res = 1, Q = 1; char c;
while( (c = getchar()) < 48 || c > 57)
if(c == '-') Q = -1;
if(Q) res = c - 48;
while( (c = getchar()) >= 48 && c <= 57)
res = res * 10 + c - 48;
return res * Q;
}
int n;
int val[ONE];
int Ans;
void Modit(int &a)
{
if(a < 0) a += MOD;
if(a >= MOD) a -= MOD;
}
struct power
{
int Min, MinI;
int Max, MaxI;
int MinMax, MinMaxI;
friend power operator -(power a, power b)
{
power c;
Modit(c.Min = a.Min - b.Min),
Modit(c.MinI = a.MinI - b.MinI),
Modit(c.Max = a.Max - b.Max),
Modit(c.MaxI = a.MaxI - b.MaxI),
Modit(c.MinMax = a.MinMax - b.MinMax),
Modit(c.MinMaxI = a.MinMaxI - b.MinMaxI);
return c;
}
}A[ONE];
int Sum(int a, int b)
{
return (s64)(a + b) * (b - a + 1) / 2 % MOD;
}
void Solve(int L, int R)
{
if(L == R)
{
Modit(Ans += (s64)val[L] * val[R] % MOD * 1);
return;
}
int mid = L + R >> 1;
int minn = INF, maxx = -INF;
A[mid] = (power){0, 0, 0, 0, 0, 0};
for(int j = mid + 1; j <= R; j++)
{
minn = min(minn, val[j]), maxx = max(maxx, val[j]),
Modit(A[j].Min = A[j - 1].Min + minn),
Modit(A[j].MinI = A[j - 1].MinI + (s64)minn * j % MOD),
Modit(A[j].Max = A[j - 1].Max + maxx),
Modit(A[j].MaxI = A[j - 1].MaxI + (s64)maxx * j % MOD),
Modit(A[j].MinMax = A[j - 1].MinMax + (s64)minn * maxx % MOD),
Modit(A[j].MinMaxI = A[j - 1].MinMaxI + (s64)minn * maxx % MOD * j % MOD);
}
minn = INF, maxx = -INF;
int a = mid, b = mid;
power del;
for(int i = mid; i >= L; i--)
{
minn = min(minn, val[i]), maxx = max(maxx, val[i]);
while(minn <= val[a + 1] && a + 1 <= R) a++;
while(maxx >= val[b + 1] && b + 1 <= R) b++;
if(a <= b)
{
Modit(Ans += (s64)maxx * minn % MOD * Sum(mid + 1 - i + 1, a - i + 1) % MOD);
del = A[b] - A[a];
Modit(Ans += (s64)maxx * del.MinI % MOD - (s64)maxx * del.Min % MOD * (i - 1) % MOD);
del = A[R] - A[b];
Modit(Ans += (s64)del.MinMaxI - (s64)del.MinMax * (i - 1) % MOD);
}
else
{
Modit(Ans += (s64)maxx * minn % MOD * Sum(mid + 1 - i + 1, b - i + 1) % MOD);
del = A[a] - A[b];
Modit(Ans += (s64)minn * del.MaxI % MOD - (s64)minn * del.Max % MOD * (i - 1) % MOD);
del = A[R] - A[a];
Modit(Ans += (s64)del.MinMaxI - (s64)del.MinMax * (i - 1) % MOD);
}
}
Solve(L, mid), Solve(mid + 1, R);
}
int main()
{
n = get();
for(int i = 1; i <= n; i++)
val[i] = get();
Solve(1, n);
printf("%d", Ans);
}
|
